package P46;

import org.junit.Test;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author DJ同学
 * @Date 2021/2/28 21:02
 * @Version 1.0
 * @Name 全排列
 * @Problem https://leetcode-cn.com/problems/permutations/
 *  回溯 标记
 */
public class Solution {

    @Test
    public void test(){
        List<List<Integer>> permute = permute(new int[]{3, 1, 2});
        return;
    }

    List<List<Integer>> list = new ArrayList<>();
    int[] flag;
    public List<List<Integer>> permute(int[] nums) {
        flag = new int[nums.length];
        dfs(0,nums.length,new ArrayList<>(),nums);
        return list;
    }

    private void dfs( int step, int end,List<Integer> temp,int[] nums) {
        if(step==end){
            list.add(new ArrayList<>(temp));//生成一个新的对象，内容和temp一样，地址不一样
            return;
        }
        for (int i = 0; i < end; i++) {
            if(flag[i]==0){
                flag[i]=1;
                temp.add(nums[i]);
                dfs(step+1,end,temp,nums);
                flag[i]=0;
                temp.remove(temp.size()-1);
            }
        }
    }
}
